package com.ocean.greedy.easy;

import java.util.Arrays;

/**
 * https://leetcode.cn/problems/largest-perimeter-triangle/
 * <p>
 * 三角形最大周长
 * <p>
 * 定由一些正数（代表长度）组成的数组 nums，返回 由其中三个长度组成的、面积不为零的三角形的最大周长。
 * 如果不能形成任何面积不为零的三角形，返回0。
 * <p>
 * <p>
 * <p>
 * 示例 1：
 * <p>
 * 输入：nums = [2,1,2]
 * 输出：5
 * 解释：你可以用三个边长组成一个三角形:1 2 2。
 * 示例 2：
 * <p>
 * 输入：nums = [1,2,1,10]
 * 输出：0
 * 解释：
 * 你不能用边长 1,1,2 来组成三角形。
 * 不能用边长 1,1,10 来构成三角形。
 * 不能用边长 1、2 和 10 来构成三角形。
 * 因为我们不能用任何三条边长来构成一个非零面积的三角形，所以我们返回 0。
 * <p>
 * <p>
 * 提示：
 * <p>
 * 3 <= nums.length <= 104
 * 1 <= nums[i] <= 106
 *
 * @author linmiaolai@sanyygp.com<br>
 * @version 1.0<br>
 * @date 2023/02/21 <br>
 */
public class LargestPerimeterTriangle {
    public static void main(String[] args) {
        LargestPerimeterTriangle triangle = new LargestPerimeterTriangle();
        int[] nums = {2, 1, 2};
        int[] nums2 = {1, 2, 1, 10};
        int[] nums3 = {1, 2, 10, 10};
        int res = triangle.largestPerimeter(nums);
        System.out.println(res);
        res = triangle.largestPerimeter(nums2);
        System.out.println(res);
        res = triangle.largestPerimeter(nums3);
        System.out.println(res);
    }

    public int largestPerimeter(int[] nums) {
        // 先选出最大的边
        // 如果另外两条边的和比最大的边大 则可以构成三角型
        Arrays.sort(nums);
        // 使用3个指针
        int m = nums.length;
        for (int i = m - 1; i >= 2; i--) {
            int k = i - 1;
            int j = i - 2;
            if ((nums[k] + nums[j] > nums[i])){
                return (nums[k] + nums[j] + nums[i]);
            }
        }
        return 0;
    }
}
